package com.cn.algorithm02.class16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/***
 * @author: hels
 * @description: 付费题目：二位数组中的岛问题- https://leetcode.cn/problems/number-of-islands-ii/
 * 给定一个m*n都为0的二维数组，给定一个位置数组int[][2](每个元素表示一个位置变为1，mn数组每次添加一个1元素返回岛屿的数量)
 **/
public class C04_NumberOfIslandsii {

    public static List<Integer> numIslands(int m, int n, int[][] position) {
        List<Integer> res = new ArrayList<>();
        UnionFind uf = new UnionFind(m, n);
        for (int[] p : position) {
            res.add(uf.coonnect(p[0], p[1]));
        }

        return res;
    }

    public static class UnionFind {
        private int[] parents;
        private int[] size;
        private int[] help;
        private int sets;
        private final int row;
        private final int col;

        public UnionFind(int m, int n) {
            row = m;
            col = n;
            int N = m * n;
            sets = 0;
            parents = new int[N];
            size = new int[N];
            help = new int[N];
        }

        //        寻找祖先，路径压缩
        public int findAncesstor(int cur) {
            int hi = 0;
            if (cur != parents[cur]) {
                help[hi++] = cur;
                cur = parents[cur];
            }
            for (hi--; hi >= 0; hi--) {
                parents[help[hi]] = cur;
            }
            return cur;
        }

        //        合并新增点位
        public int coonnect(int r, int c) {
            int i = index(r, c);
//            当rc位置为0时表示没有进行改1操作，可以进行合并操作
            if (size[i] == 0) {
                parents[i] = i;
                size[i] = 1;
                sets++;
                union(r, c, r - 1, c);
                union(r, c, r + 1, c);
                union(r, c, r, c - 1);
                union(r, c, r, c + 1);
            }
            return sets;
        }

        //        域合并
        public void union(int r1, int c1, int r2, int c2) {
            if (r1 < 0 || r1 == row || c1 < 0 || c1 == col || r2 < 0 || r2 == row || c2 < 0 || c2 == col) {
                return;
            }
            int i1 = index(r1, c1);
            int i2 = index(r2, c2);
            if (parents[i1] == 0 || parents[i2] == 0) {
                return;
            }
            int f1 = findAncesstor(i1);
            int f2 = findAncesstor(i2);
            if (f1 != f2) {
                if (f1 >= f2) {
                    parents[f2] = f1;
                    size[f1] = size[f1] + size[f2];
                } else {
                    parents[f1] = f2;
                    size[f2] = size[f1] + size[f2];
                }
                sets--;
            }
        }

        public int index(int r, int c) {
            return r * col + c;
        }

        public int sets() {
            return sets;
        }
    }


}
